package 快速幂;

class Solution {
    //初次尝试版
    public double myPow1(double x, int n) {
        if(n == 0){
            return 1.0;
        }
        if (n > 0){
            if(n == 1){
                return x;
            }
            double tmp = myPow1(x, n / 2);
            if (n % 2 != 0){
                return tmp * tmp * x;
            }
            return tmp * tmp;
        }else{
            if(n == -1){
                return 1/x;
            }
            double tmp = myPow1(x, n / 2);
            if (n % 2 != 0){
                return tmp * tmp * (1 / x);
            }
            return tmp * tmp;
        }
    }

    //优化改良版
    public double myPow(double x, int n) {
        return n < 0 ? 1 / pow(x, (long)-n) : pow(x, n);
    }

    public double pow(double x, long n){
        if(n == 0){
            return 1.0;
        }
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
}